home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 4_0 / DIZZY / SRC / PNTONLIN.C < prev    next >
Text File  |  1990-12-28  |  2KB  |  63 lines
  1. /* 
  2. A Fast 2D Point-On-Line Test
  3. by Alan Paeth
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. #include "graphicsgems.h"
  8.  
  9. int PntOnLine(px,py,qx,qy,tx,ty)
  10.    long px, py, qx, qy, tx, ty;
  11.    {
  12. /*
  13.  * given a line through P:(px,py) Q:(qx,qy) and T:(tx,ty)
  14.  * return 0 if T is not on the line through      <--P--Q-->
  15.  *          1 if T is on the open ray ending at P: <--P
  16.  *          2 if T is on the closed interior along:    P--Q
  17.  *          3 if T is on the open ray beginning at Q:    Q-->
  18.  *
  19.  * Example: consider the line P = (3,2), Q = (17,7). A plot
  20.  * of the test points T(x,y) (with 0 mapped onto '.') yields:
  21.  *
  22.  *       8| . . . . . . . . . . . . . . . . . 3 3
  23.  *    Y  7| . . . . . . . . . . . . . . 2 2 Q 3 3    Q = 2
  24.  *       6| . . . . . . . . . . . 2 2 2 2 2 . . .
  25.  *    a  5| . . . . . . . . 2 2 2 2 2 2 . . . . .
  26.  *    x  4| . . . . . 2 2 2 2 2 2 . . . . . . . .
  27.  *    i  3| . . . 2 2 2 2 2 . . . . . . . . . . .
  28.  *    s  2| 1 1 P 2 2 . . . . . . . . . . . . . .    P = 2
  29.  *       1| 1 1 . . . . . . . . . . . . . . . . .
  30.  *        +--------------------------------------
  31.  *          1 2 3 4 5 X-axis 10         15      19
  32.  *
  33.  * Point-Line distance is normalized with the Infinity Norm
  34.  * avoiding square-root code and tightening the test vs the
  35.  * Manhattan Norm. All math is done on the field of integers.
  36.  * The latter replaces the initial ">= MAX(...)" test with
  37.  * "> (ABS(qx-px) + ABS(qy-py))" loosening both inequality
  38.  * and norm, yielding a broader target line for selection.
  39.  * The tightest test is employed here for best discrimination
  40.  * in merging collinear (to grid coordinates) vertex chains
  41.  * into a larger, spanning vectors within the Lemming editor.
  42.  */
  43.  
  44.  
  45.     if ( ABS((qy-py)*(tx-px)-(ty-py)*(qx-px)) >=
  46.         (4*MAX(ABS(qx-px), ABS(qy-py)))) return(0);
  47.     if (((qx<px)&&(px<tx)) || ((qy<py)&&(py<ty))) return(1);
  48.     if (((tx<px)&&(px<qx)) || ((ty<py)&&(py<qy))) return(1);
  49.     if (((px<qx)&&(qx<tx)) || ((py<qy)&&(qy<ty))) return(3);
  50.     if (((tx<qx)&&(qx<px)) || ((ty<qy)&&(qy<py))) return(3);
  51.     return(2);
  52.     }
  53.  
  54. /*    Note:
  55. **    Modified to test line distance of several pixels by adding
  56. **    multiplication by 4 to distance calculation approximation.
  57. **    This allows a distance of 2 pixels from the line to be
  58. **    accepted.    -- Modification by Juri Munkki    12/8/90
  59. **
  60. **    The source code in Graphics Gems is explicitly put in Public
  61. **    Domain. This modified version is also in the public domain.
  62. */
  63.